package com.leet.code;

import org.junit.Test;

import java.util.Arrays;

public class Code204 {

    @Test
    public void test() {
        int i = countPrimes(10);
        System.out.println(i);
    }


    public int countPrimes(int n) {
        int[] isPrime = new int[n];
        Arrays.fill(isPrime, 1);
        int ans = 0;
        for (int i = 2; i < n; ++i) {
            if (isPrime[i] == 1) {
                ans += 1;
                long p = (long) i * i;
                if (p < n) {
                    for (int j = (int) p; j < n; j += i) {
                        isPrime[j] = 0;
                    }
                }
            }
        }
        return ans;
    }


}
